package com.leetcode;

import com.leetcode.common.TreeNode;
import com.leetcode.util.BinaryTreeUtil;

/**
 * 450. 删除二叉搜索树中的节点
 * 1. 找到待删除的节点
 * 2. 将待删除当前节点替换为以当前节点为根节点的树中最小的节点
 *
 * @author fy
 * @date 2022/4/26 15:09
 */
public class Solution450 {

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val > key) {
            // 待删除的节点在左子树
            root.left = deleteNode(root.left, key);
        } else if (root.val < key) {
            // 待删除的节点在右子树
            root.right = deleteNode(root.right, key);
        } else {
            // 如果当前节点就是待删除的节点
            // 当待删除节点左子树为空, 则直接返回用右子树替换
            if (root.left == null) {
                return root.right;
            }
            // 当待删除节点右子树为空, 则直接返回用左子树替换
            if (root.right == null) {
                return root.left;
            }
            // 待删除节点左右子树都不为空, 则从右子树中找最小的节点代替当前节点. 并在右子树中删除该最小节点
            // 这里只改值, 没有新创建节点
            TreeNode moveNode = findMin(root.right);
            root.right = deleteNode(root.right, moveNode.val);
            root.val = moveNode.val;
        }
        return root;
    }

    private TreeNode findMin(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }


    public static void main(String[] args) {
        TreeNode root = BinaryTreeUtil.createTree(new Integer[]{5, 3, 6, 2, 4, null, 7});
        BinaryTreeUtil.printTree(root);

        TreeNode newRoot = new Solution450().deleteNode(root, 5);
        BinaryTreeUtil.printTree(newRoot);
    }

}
